/*
 * Copyright (c) 2018. J4dream created
 */

package com.j4dream.property.leetcode.basic;

import com.j4dream.property.leetcode.basic.article.ListNode;

public class LinkListBasic {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0);
        ListNode t = node;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                node.next = l1;
                l1 = l1.next;
            } else {
                node.next = l2;
                l2 = l2.next;
            }
            node = node.next;
        }

        if (l1 == null) {
            node.next = l2;
        }
        if (l2 == null) {
            node.next = l1;
        }
        return t.next;
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        ListNode middle = head;
        int count = 0;
        ListNode curr = head;
        while (curr != null) {
            if (count > 1 && count % 2 == 0) {
                middle = middle.next;
            }
            count++;
            curr = curr.next;

        }
        ListNode pre = null;
        curr = middle.next;
        ListNode temp;
        while (curr != null) {
            temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }
        middle.next = pre;

        curr = pre;
        while (curr != null) {
            if (curr.val != head.val) {
                return false;
            }
            curr = curr.next;
            head = head.next;
        }
        return true;
    }

    // 快慢指针
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode quickNode = head.next;
        ListNode slowNode = head;
        while (quickNode != null && quickNode.next != null && slowNode != null) {
            if (quickNode == slowNode) {
                return true;
            }
            quickNode = quickNode.next.next;
            slowNode = slowNode.next;
        }
        return false;
    }
}
